Pencarian tabu

Pencarian Tabu (bahasa Inggris: Tabu Search; TS) adalah metode pencarian metaheuristik yang menggunakan metode pencarian lokal untuk optimasi matematis. Algoritma ini dibuat oleh Fred W. Glover pada tahun 1986^[1] dan diformalisasi pada tahun 1989.^[2][3]

Pencarian lokal (ketetanggaan) mengambil solusi potensial terhadap suatu masalah dan memeriksa tetangga terdekatnya (yaitu, solusi yang serupa kecuali untuk beberapa detail kecil) dengan harapan menemukan solusi yang lebih baik. Metode pencarian lokal seringkali terjebak di daerah suboptimal atau dataran tinggi dengan banyak solusi yang sama-sama cocok.

Pencarian Tabu meningkatkan kinerja pencarian lokal dengan melonggarkan aturan dasarnya. Pertama, pada setiap langkah, pergerakan yang memburuk dapat diterima jika tidak ada pergerakan yang lebih baik (seperti ketika pencarian terhenti pada minimum lokal yang ketat). Selain itu, larangan (sehingga, istilah tabu) diperkenalkan untuk mencegah pencarian kembali ke solusi yang telah dikunjungi sebelumnya.

Implementasi pencarian tabu menggunakan struktur memori yang menggambarkan solusi yang dikunjungi atau seperangkat aturan yang disediakan pengguna.^[2] Jika suatu solusi potensial telah dikunjungi sebelumnya dalam jangka waktu pendek tertentu atau jika telah melanggar suatu aturan, maka solusi tersebut ditandai sebagai “tabu” (terlarang) sehingga algoritma tidak mempertimbangkan kemungkinan tersebut berulang kali.

1. ^ Fred Glover (1986). "Future Paths for Integer Programming and Links to Artificial Intelligence". Computers and Operations Research. 13 (5): 533–549. doi:10.1016/0305-0548(86)90048-1. 
2. ^ ^{a b} Fred Glover (1989). "Tabu Search – Part 1". ORSA Journal on Computing. 1 (2): 190–206. doi:10.1287/ijoc.1.3.190. 
3. ^ Fred Glover (1990). "Tabu Search – Part 2". ORSA Journal on Computing. 2 (1): 4–32. doi:10.1287/ijoc.2.1.4.